// MarkovAlg.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include "hashFunctionNoCase.h"
#include "myutil.h"

#include <fstream>
#include <iostream>
#include <string>
#include <locale>
#include <cstdlib>
#include <assert.h>

#include <boost/unordered_map.hpp>

using namespace std;

typedef std::pair<string, string> Prefix;
typedef string Suffix;

struct HashElement
{
   Prefix mPrefix;
   Suffix mSuffix;

   HashElement(const Prefix& pre, const Suffix& suf) : mPrefix(pre), mSuffix(suf)  { }
};

typedef boost::unordered_multimap<string, HashElement, hash_examples::ihash, hash_examples::iequal_to> MarkovStateMap;
//typedef boost::unordered_multimap<string, HashElement> MarkovStateMap;

static const string sStopMarker = "!$t0p!";
static const int MAX_WORD = 1000;

// ----------------------------------------------------------------------------
// void addToTable(MarkovStateMap & preSuffTable, const Prefix & prefix , const Suffix & suf)
void addToTable(MarkovStateMap & preSuffTable, const string & first, const string & second, const string & suf)
{
   Prefix prefix;
   prefix.first = first;
   prefix.second = second;

   HashElement elt(prefix, suf);
   string index = prefix.first + prefix.second;

   cout <<"adding: '" <<index <<"'  -->  '" <<suf <<"'" <<endl;

   MarkovStateMap::iterator it = preSuffTable.insert( std::pair<string, HashElement>(index, elt) );
   assert(it != preSuffTable.end());
}

static void goMarkov(MarkovStateMap & store, const Prefix &start)
{
   const string *pre1 = &start.first, *pre2 = &start.second, *suff = 0;

   bool done = false;
   cout <<endl;
   int wordCt = 0;

   cout <<start.first <<" " <<start.second;
   while (! done && wordCt < MAX_WORD)
   {
      string key = *pre1 + *pre2;

      std::pair<MarkovStateMap::const_iterator, MarkovStateMap::const_iterator> bucketIt = store.equal_range(key);
//      cout <<"Number of elemement with key:" <<key <<" - " <<bucketIt.first - bucketIt.second <<endl; // store.count(key) <<endl;
      // suffixes
      int count = 0;
      int expecting = store.count(key);

#if 0
 //     if ( (bucketIt.first == store.end()) || (bucketIt.second == store.end()) )
      {
         cout <<"[key:'" <<key <<"'][ct:" <<store.count(key) <<"][1st:"
            <<(bucketIt.first == store.end() ? "NULL" : "not")
            <<"][2nd:"
            <<(bucketIt.second == store.end() ? "NULL" : "not")
            <<"][1st==2nd:" <<(bucketIt.first == bucketIt.second ? "T" : "F" )
            <<']'
            <<endl;
//         assert(0);
      }
#endif

      for (MarkovStateMap::const_iterator it = bucketIt.first; it != bucketIt.second; ++it)
      {
         if (it->second.mSuffix == sStopMarker)
         {
            done = true;
            break;
         }
         count++;
         wordCt++;

         assert(count <= expecting);
         if (! noCaseStringIsEqual(it->first, key))
         {
            cout <<"key:" <<key <<"  - table-key:" <<it->first <<endl;
            assert(0);
         }
         // there is a bug in the unordered_map::equal_range whereby if we call it for only one item, the 2nd iterator is null.
         // what gives???
      }

      if (! done)
      {
         if (count > 1)
         {
            int choose = rand() % count;
            for (int i=0; i < choose; i++, bucketIt.first++)
            {
            }
         }
         pre1 = pre2;
         pre2 = &bucketIt.first->second.mSuffix;
         cout << " " << *pre2;
      }
   }
   cout <<endl;
}

// ----------------------------------------------------------------------------
int main(int argc, char* argv[])
{
   if (argc == 1 || argv[1] == NULL || *argv[1] == 0)
   {
      char ch=0;
      cout << "Usage: " << argv[0] <<" <file-name>" <<endl;
      cin >> ch;
   }

   srand( static_cast<unsigned int>(time(NULL)) );

   // ***************
   // Build the data structure:
   //    1) read each words, separated by whitespaces: <space> <tab> <nl>
   //    2) take the beginning first two words, the prefix, followed by one word, the suffix
   //    3) the prefix is the key in the hash table, the suffix is the value
   //    4) remove the 1st word of the prefix and repeat 2 & 3
   // Construct new phrases:
   //    1) Markov Chain Algorithm:
   //       Set w1 and w2 to the first two words in the text
   //       print w1 and w2
   //       loop:
   //          randomly choose w3, one of the successors to prefix w1 w2 in the text
   //          print w3
   //          replace w1 and w2 by w2 and w3
   //          repeat loop
   // ***************

   ifstream file;
   MarkovStateMap store;

   cout <<"bucket count: " <<store.bucket_count() <<"/" <<store.max_bucket_count() <<endl;
   cout <<"max-load-factor: " <<store.max_load_factor() <<endl;
//   store.max_load_factor(3.0);
//   cout <<"max-load-factor: " <<store.max_load_factor() <<endl;

   Prefix startPrefix;
   // for all command-line arguments
   for (int i=1; i<argc; ++i)
   {
      file.open(argv[i]);

      Suffix suf;
      string buf1, buf2, buf3;
      string *pre1 = &buf1, *pre2 = &buf2, *suff = &buf3;

      if ((file >> *pre1) && (file >> *pre2))
      {
         startPrefix.first = *pre1;
         startPrefix.second = *pre2;

         while (file >> *suff)
         {
            if (file.fail())
               break;
            // have prefix and suffix, now put into hash table
            addToTable(store, *pre1, *pre2, *suff);
            string * tmp = pre1;
            pre1 = pre2;
            pre2 = suff;
            suff = tmp;
         }

         if (! file.eof())
         {
            cout <<"Input error in file: '" <<argv[i] <<"'" <<endl;
         }

         addToTable(store, *pre1, *pre2, sStopMarker);
      }

      if (! file.eof())
      {
         cout <<"Input error in file: '" <<argv[i] <<"'" <<endl;
      }

      // clear eofbit and failbit set due to end-of-file
      file.clear();

      // close file
      file.close();
   }

   cout <<"bucket-count:" <<store.bucket_count() <<" \n";

   // ********************
   // Print the results
   // ********************
   cout <<"\n";
/*
   for (MarkovStateMap::const_iterator i = store.begin(); i != store.end(); i++)
   {
      const HashElement & elt = i->second;
      cout <<elt.mPrefix.first <<" " <<elt.mPrefix.second <<"  ==>  " <<elt.mSuffix <<endl;
   }
*/
   if (! startPrefix.first.empty() && ! startPrefix.second.empty())
   {
      goMarkov(store, startPrefix);
   }

	return 0;
}

